/**
 * @a https://leetcode.cn/problems/sort-an-array/description/
 */


#include "common.h"

class Solution
{
private:
    vector<int> nums; // 将数组作为类的成员变量
    vector<int> tmp;  // 临时数组也作为成员变量，避免反复创建

public:
    vector<int> sortArray(vector<int> &nums)
    {
        this->nums = nums;             // 初始化成员变量
        this->tmp.resize(nums.size()); // 预分配临时数组空间
        mergeSort(0, nums.size());     // 调用归并排序
        return this->nums;             // 返回排序后的数组
    }

    void mergeSort(int l, int r)
    {
        if (r - l <= 1)
            return;                // 如果区间长度 <= 1，直接返回
        int mid = l + (r - l) / 2; // 计算中间点
        mergeSort(l, mid);         // 递归排序左半部分 [l, mid)
        mergeSort(mid, r);         // 递归排序右半部分 [mid, r)
        merge(l, mid, r);          // 合并两个有序区间
    }

    void merge(int l, int mid, int r)
    {
        int cur1 = l, cur2 = mid;
        int i = l; // 临时数组的起始位置
        // 合并两个有序区间
        while (cur1 < mid && cur2 < r)
        {
            tmp[i++] = (nums[cur1] < nums[cur2]) ? nums[cur1++] : nums[cur2++];
        }
        // 处理剩余元素
        while (cur1 < mid)
            tmp[i++] = nums[cur1++];
        while (cur2 < r)
            tmp[i++] = nums[cur2++];
        // 将临时数组拷贝回原数组
        for (int k = l; k < r; k++)
        {
            nums[k] = tmp[k];
        }
    }
};